#clean the code from unuseful stuff
def clean_code(line):
	#removes all the comments
	line = line.replace(line[line.find("#"):line.find("\n")], "");
	#removes all the \n to make the code compact
	line = line.replace("\n","");
	#removes all the \t to make the code compact
	line = line.replace("\t"," ");
	return line
	
	
#recognize an instruction and split it into a list of elements like ['move','$regA,'$regB']
def instruction_split(line):
	line = filter(None, line.split(" "))
	for	elem in line:
		line2 = filter(None, elem.split(","))
		if len(line2)!=1:
			line.pop(line.index(elem))
			line = line + line2
	return line
	
	
#recognize an instruction and join it into assembler mode
def instruction_join(lineinlist):
	line=""
	if len(lineinlist)>2:
		for	elem in lineinlist:
			if lineinlist[0][0]!="." or lineinlist[0]==".frame" or lineinlist[0]==".mask" or lineinlist[0]==".fmask":
				if lineinlist.index(elem)==0:
					line="    "+lineinlist[0]+" "
				elif lineinlist.index(elem)==len(lineinlist)-1:
					line=line+lineinlist[lineinlist.index(elem)]
				else:
					line=line+lineinlist[lineinlist.index(elem)]+","
			else:# lineinlist[0][0]=="." and lineinlist[0]!=".frame" and lineinlist[0]!=".mask" and lineinlist[0]!=".fmask":
				if lineinlist.index(elem)==0:
					line="    "+lineinlist[0]+" "
				elif lineinlist.index(elem)==len(lineinlist)-1:
					line=line+lineinlist[lineinlist.index(elem)]
				else:
					line=line+lineinlist[lineinlist.index(elem)]+" "			
	elif len(lineinlist)==2:
		line="    "+lineinlist[0]+" "+lineinlist[1]
	elif len(lineinlist)<2 and len(lineinlist)>0:
		if lineinlist[0][0]!=".":
			line=lineinlist[0]
		else:
			line="    "+lineinlist[0]
	else:
		line=lineinlist[0]
	return line
	
#pop a number of elements that you decide from a list item you choose
'''def poplist_from_index_for_numelem(content,index,numelem):
	for i in range(int(index+1),int(index+numelem+1)):
		content.pop(i)
		content.insert(i,instruction_join(["\n"])) 
	return int(i)

#return the line number of a jump instruction
def jump_to_line(content,linepass,registers):
	if linepass[0]=="j": # or linepass[0]=="jal":
		registers = pop_dead_registers(registers)
		#print "********trovata jump!!!!"
		for i in range(0,len(content)):
			line = content[i]
			line = clean_code(line)
			linex = instruction_split(line)
			#print "--->"+str(linex)
			if line.rstrip():
				if(linex[0]==linepass[1]+":"):
					#print "Sono Ugualiiiiii vado alla riga --->"+str(i)
					return [i,registers]
		return False
	else:
		#print False
		return False
	
#return the line number of a branch instruction
def branch_to_line(content,linepass,registers):
	if linepass[0]=="bne":
		#print "********trovata branch!!!!"
		if int(register_value(linepass[1],registers))!=int(register_value(linepass[2],registers)):
			#print "ENTRATTTTTTOOOO"
			registers = pop_dead_registers(registers)
			for i in range(0,len(content)):
				line = content[i]
				line = clean_code(line)
				linex = instruction_split(line)
				#print "--->"+str(linex)
				if line.rstrip():
					if(linex[0]==linepass[3]+":"):
						#print "Sono diversiiiii vado alla riga --->"+str(i)
						return [i,registers]
		else:
			return False
	elif linepass[0]=="beq":
		#print "********trovata branch!!!!"
		if int(register_value(linepass[1],registers))==int(register_value(linepass[2],registers)):
			#print "ENTRATTTTTTOOOO"
			registers = pop_dead_registers(registers)
			for i in range(0,len(content)):
				line = content[i]
				line = clean_code(line)
				linex = instruction_split(line)
				#print "--->"+str(linex)
				if line.rstrip():
					if(linex[0]==linepass[3]+":"):
						#print "Sono diversiiiii vado alla riga --->"+str(i)
						return [i,registers]
		else:
			return False
	else:
		#print False
		return False

#pop dead registers
def pop_dead_registers(registers):
	length=len(registers)
	for i in range(0,length):
		if i<length :
			if registers[i][0]=="$4" or registers[i][0]=="$5" or registers[i][0]=="$6" or registers[i][0]=="$7" or registers[i][0]=="$8" or registers[i][0]=="$9" or registers[i][0]=="$10" or registers[i][0]=="$11" or registers[i][0]=="$12" or registers[i][0]=="$14" or registers[i][0]=="$15" or registers[i][0]=="$24" or registers[i][0]=="$25":
				#print "Register POP of --->!!!"+str(registers[i])
				registers.pop(i)
				length=length-1
	return registers
	
#dataflow analysis
def dataflow_analysis(lineinlist,registers):
	if len(lineinlist)>2 and len(registers)>0:
		for i in range(0,len(registers)):
			#print i
			#print str(registers[i][0])+"=="+lineinlist[1]
			#print str(i)+"=="+str(len(registers))
			if registers[i][0]==lineinlist[1] and lineinlist[0]!="sw":
				#print "modifico"
				value=mips_operations(lineinlist,registers) #qua ci va una funzione che fa i calcoli ogni volta
				if(value!=None):
					registers[i][1]=value
				break 
			elif registers[i][0]==lineinlist[2] and lineinlist[0]=="sw":
				value=mips_operations(lineinlist,registers) #qua ci va una funzione che fa i calcoli ogni volta
				if(value!=None):
					registers[i][1]=value				
				break
			elif i==len(registers)-1 and lineinlist[0]!="sw":
				#print "appendo"
				value=mips_operations(lineinlist,registers) #qua ci va una funzione che fa i calcoli ogni volta
				if(value!=None):
					registers.append([lineinlist[1],value]) 
				break
			elif i==len(registers)-1 and lineinlist[0]=="sw":
				#print "appendo"
				value=mips_operations(lineinlist,registers) #qua ci va una funzione che fa i calcoli ogni volta
				if(value!=None):
					registers.append([lineinlist[2],value]) 
				break
	return registers

# understands mips operations and return the value for them	
def mips_operations(lineinlist,registers):
	if len(lineinlist)>2 and len(registers)>0:
		if lineinlist[0]=="addu" or lineinlist[0]=="addi" or lineinlist[0]=="add" or lineinlist[0]=="addiu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))+int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="subu" or lineinlist[0]=="sub":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))-int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="mul" or lineinlist[0]=="mult" or lineinlist[0]=="multu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))*int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="div" or lineinlist[0]=="divu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))/int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="li":
			#print "##################******************"+str(lineinlist[len(lineinlist)-2])+"="+str(int(lineinlist[len(lineinlist)-1],0))
			return int(lineinlist[len(lineinlist)-1],0)
		elif lineinlist[0]=="slt" or lineinlist[0]=="slti" or lineinlist[0]=="sltu" or lineinlist[0]=="sltiu":
			#print "**************************"+str(int(register_value(lineinlist[len(lineinlist)-2],registers)))+"<"+str(int(register_value(lineinlist[len(lineinlist)-1],registers)))
			if(int(register_value(lineinlist[len(lineinlist)-2],registers))<int(register_value(lineinlist[len(lineinlist)-1],registers))):
				return 1
			else:
				return 0
		elif lineinlist[0]=="mov" or lineinlist[0]=="move":
			return int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="sw":
			return int(register_value(lineinlist[1],registers))
		elif lineinlist[0]=="lw":
			return int(register_value(lineinlist[len(lineinlist)-1],registers))
		else:
			return None
			
#get the actual value of a register and return it
def register_value(element, registers):
	#pop the default element that we don't use
	if(registers[0][0]==0 and registers[0][1]==0 and len(registers)>=2):
		registers.pop(0)
	#check for all the registers stored in the list
	for i in range(0,len(registers)):
		#print element+"--->"+str(element.isdigit())
		if registers[i][0] == element and not element.isdigit():
			#print registers[i][0]+"**********="+str(registers[i][1])
			return registers[i][1]
		elif registers[i][0] != element and element.isdigit():
			#print "*******************************="+str(int(element))
			return int(element)
	return 0
'''					
#removes the instruction shift $regA,$regA,0
def shift_regA_regA_0(lineinlist):
	if len(lineinlist)==4:
		#print lineinlist
		if (lineinlist[0] == "sll" or lineinlist[0] == "sla" or lineinlist[0] == "srl" or lineinlist[0] == "sra" )  and lineinlist[1] == lineinlist[2] and lineinlist[3]=="0":
			return "# ERASED --> " + instruction_join(lineinlist)
	return instruction_join(lineinlist) 
	

#change the instructions move $regA,$regB & instr $regA,$regA,... INTO instr $regA,$regB,...
def instr_regA_regB_other(lineinlist,lineinlist2):
	if len(lineinlist)==3 and len(lineinlist2)>=4:
		if lineinlist[0] == "move" and (lineinlist2[0] == "move" or lineinlist2[0] == "mov" or lineinlist2[0] == "add" or lineinlist2[0] == "addu" or lineinlist2[0] == "addiu" or lineinlist2[0] == "addi" or lineinlist2[0]=="subu" or lineinlist2[0]=="sub" or lineinlist2[0]=="mul" or lineinlist2[0]=="mult" or lineinlist2[0]=="multu" or lineinlist2[0]=="div" or lineinlist2[0]=="divu" or lineinlist2[0]=="li")  and lineinlist[1] == lineinlist2[1] and lineinlist[1]==lineinlist2[2]:
			output=instruction_join([lineinlist2[0],lineinlist[1],lineinlist[2],lineinlist2[3]])#+" ###### MODIFIED ---> [move $regA,$regB] & [instr $regA,$regA]"
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]

#change the instructions [sw $regA,XXX] & [ld $regA,XXX],... INTO [sw $regA,XXX]
def sw_regA_XXX(lineinlist,lineinlist2):
	if len(lineinlist)>=3 and len(lineinlist2)>=3:
		if lineinlist[0] == "sw" and lineinlist2[0] == "ld"  and lineinlist[1] == lineinlist2[1] and lineinlist[2]==lineinlist2[2]:
			output=instruction_join([lineinlist[0],lineinlist[1],lineinlist[2]])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#change the instructions [add $regA,$regA,X] & [lw ...,0($regA)],... INTO [lw ...,X($regA)]
def lw_XXX_XregA(lineinlist,lineinlist2):
	if len(lineinlist)>=4 and len(lineinlist2)>=3:
		if lineinlist[0] == "addu" and lineinlist2[0] == "lw"  and "0("+lineinlist[1]+")" == lineinlist2[2] and lineinlist[3].isdigit():
			output=instruction_join([lineinlist2[0],lineinlist2[1],lineinlist[3]+"("+lineinlist[1]+")"])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#change the instructions [beq ...,$Lx] & [j $Ly] & [$Lx: ...] INTO [bne ...,$Ly] & [$Lx:]
def bne_XXX_ly(lineinlist,lineinlist2):
	if len(lineinlist)>=4 and len(lineinlist2)==2:
		if lineinlist[0] == "beq" and lineinlist2[0] == "j" and lineinlist[3]!=lineinlist2[1]:
			output=instruction_join(["bne",lineinlist[1],lineinlist[2],lineinlist2[1]])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#change the instructions [instr $regA,...] & [mov $4,$regA] & [jal XXX] INTO [instr $4,...] & [jal XXX]
def instr_4_XXX(lineinlist,lineinlist2):
	if len(lineinlist)>=4 and len(lineinlist2)==3:
		if (lineinlist[0] == "move" or lineinlist[0] == "mov" or lineinlist[0] == "add" or lineinlist[0] == "addu" or lineinlist[0] == "addiu" or lineinlist[0] == "addi" or lineinlist[0]=="subu" or lineinlist[0]=="sub" or lineinlist[0]=="mul" or lineinlist[0]=="mult" or lineinlist[0]=="multu" or lineinlist[0]=="div" or lineinlist[0]=="divu" or lineinlist[0]=="li") and (lineinlist2[0] == "move" or lineinlist2[0] == "mov") and lineinlist[1]==lineinlist2[2] and (lineinlist2[1]=="$4" or lineinlist2[1]=="$5" or lineinlist2[1]=="$6" or lineinlist2[1]=="$7") :
			output=instruction_join([lineinlist[0],lineinlist2[1],lineinlist[2],lineinlist[3]])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#removes the instruction  move_regA_regB
def move_regA_regB(lineinlist,registers):
	if len(lineinlist)==3:
		#print lineinlist
		if (lineinlist[0] == "move" or lineinlist[0] == "move")  and int(register_value(lineinlist[1],registers)) == int(register_value(lineinlist[2],registers)):
			#print "************* ERASED because "+lineinlist[1]+"="+str(int(register_value(lineinlist[1],registers)))+"=="+lineinlist[2]+"="+str(int(register_value(lineinlist[2],registers)))
			return "# ERASED --> " + instruction_join(lineinlist)
	return instruction_join(lineinlist)

#removes lines of code if [j $L4] & [$L4:] (so if they are consecutive) into [$L4:]
'''def jump_L4_L4(lineinlist,lineinlist2):
	#print str(lineinlist)+"-->"+str(lineinlist2)
	if len(lineinlist)==2 and len(lineinlist2)==1:
		if lineinlist[0] == "j" and lineinlist[1]+":"==lineinlist2[0]:
			#print "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"
			output=instruction_join([lineinlist2[0]])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#transform lines of code if [$L4:] & [$L2:] (so if they are consecutive) into [$L2:]
def del_L4_L2(lineinlist,lineinlist2):
	if len(lineinlist)==1 and len(lineinlist2)==1:
		if lineinlist[0]!=lineinlist2[0]:
			output=instruction_join([lineinlist2[0]])
			skipnuminstr=1
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]

	
#check for an element inside a multidimensional list
def search_element(element, multilist):
	#check for all the elements stored in the list
	p=0
	for i in multilist:
		if i[0] == element:
			return int(p)
		p+=1
	return False
	
#create a list with the optimized files instructions
def optimized_list(optlist,instr,linenum,newfile):
	if len(optlist)>0:
		#pop the default element that we don't use
		if(optlist[0][0]==0 and optlist[0][1]==0):
			optlist.pop(0)
		if not search_element(linenum, optlist):
			optlist.insert(linenum,[int(linenum),instr])
			#print optlist			
	return optlist

#create a list with the optimized files instructions
def optimized_list_into_file(optlist,newfile):
	#sort the list in place
	optlist.sort(key=operator.itemgetter(0))
	f = open(newfile, "w")
	f.close()	
	if len(optlist)>0:
		for i in optlist:
			f = open(newfile, "a")
			f.write(str(i[1])+"\n")
			f.close()
	return optlist	
'''
	
#peephole optimizer main
def peephole_optimizer(filename):
	'''registers=[[0,0]] #default value of the registers list'''
	#read a file and put it into a list
	with open(filename) as f:
		content = f.readlines()
	f.close()
	#creates a new file for the optimization
	'''jump = branch = False'''
	'''optlist=[[0,0]]'''
	#name of the new filename generated
	newfile="new"+filename
	f = open(newfile, "w")
	i=0
	while (i<len(content)):
		line = content[i]
		#clean the line from unuseful stuff
		line = clean_code(line)
		#once he find the main start to optimize
		if line.rstrip(): 
			#optimize shift_regA_regA_0
			line = shift_regA_regA_0(instruction_split(line))
			
			#optimize move_regA_regB
			'''line = move_regA_regB(instruction_split(line),registers)'''
			if i+1<len(content):
				#check the next line and clean it
				linenext=clean_code(content[i+1])#clean_code(linecache.getline(filename, i+2))#
				
				#optimize instr_regA_regB_other
				out = instr_regA_regB_other(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]
				
				#optimize sw_regA_XXX
				out = sw_regA_XXX(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]
				
				#optimize lw_XXX_XregA
				out = lw_XXX_XregA(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]

				#optimize bne_XXX_ly
				out = bne_XXX_ly(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
					#check the next line and clean it
					#linenext=clean_code(content[i+1])
				#write the new instruction in line var
				line = out[0]

				#optimize instr_4_XXX
				out = instr_4_XXX(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]
				
				'''#optimize jump_L4_L4
				out = jump_L4_L4(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]
				
				#optimize del_L4_L2
				out = del_L4_L2(instruction_split(line),instruction_split(linenext))
				#check if there is somehing else to delete from the list
				if out[1]>-1 and i+int(out[1])<len(content):
					i=poplist_from_index_for_numelem(content,i,out[1])
				#write the new instruction in line var
				line = out[0]
			
			#dataflow analisys creates a list with the active registers
			registers = dataflow_analysis(instruction_split(line),registers)
			#print registers
			
			
			#check if there is a jump and if there is jump to that label
			jump=jump_to_line(content,instruction_split(line),registers)
			
			if jump!=False:
				i=jump[0]-1
				registers=jump[1]
			
			#check if there is a jump and if there is jump to that label
			branch=branch_to_line(content,instruction_split(line),registers)
			
			if branch!=False:
				i=branch[0]-1
				registers=branch[1]
			'''
			'''optlist=optimized_list(optlist,line,i,newfile)'''
			#output the line
			print str(i)+") "+line
			#write the line into the file
			f.write(line+"\n")

		elif line.rstrip():
			#optlist=optimized_list(optlist,line,i,newfile)
			f.write(line+"\n")
		i+=1
	#close the new file
	f.close()
	#return optlist


	
#import operator
#filename must be in the same path of this file
filename = "hello.s"
#name of the new filename generated
#newfile="new"+filename
#call the optimization
peephole_optimizer(filename)
#put the optimization into a file
#optimized_list_into_file(optimizedlist,newfile)

'''

#reads the number of lines in the file
numline = len(open(filename).readlines())
bool=False
#while there is something to optimize...Optimize it!
#while(bool==False):
	#call the peephole optimizer function
	optimizedlist=peephole_optimizer(filename)
	optimized_list_into_file(optimizedlist,filename)
	# if the number of lines of the previous file it's more than the optimized one continue with optimizing
	if(numline>len(open(filename).readlines())):
		#print "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY "+str(numline)+">"+str(len(open(filename).readlines()))
		numline = len(open(filename).readlines())
	else:
		#print str(numline)+">"+str(len(open(filename).readlines()))
		#print "escoooooooooooooooooooooooooooooooooooooooooooo"
		bool=True'''
